#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : QueueReconstructionHeight.py
# @Time    : 2020/11/16 10:08
# @Description:
from typing import List


class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        """
        Suppose you have a random list of people standing in a queue. Each person is described by a pair of
        integers (h, k), where h is the height of the person and k is the number of people in front of this person
         who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

        Note:
        The number of people is less than 1,100.

        Example
            Input:
                [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
            Output:
                [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

        :param people:
        :return:
        """
        people.sort(key=lambda x: (-x[0], x[1]))
        ans = []
        for person in people:
            ans[person[1]: person[1]] = [person]
        return ans


if __name__ == '__main__':
    S = Solution()
    people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
    print(S.reconstructQueue(people))
    print('done')
